package leetcode_day._2021._202110;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/8 9:06
 * 重复的DNA序列
 * 所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 * 算法：哈希表 + 滑动窗口
 * 使用 set 来去重，map 来记录字符串出现的次数
 * set 占用空间大
 * 时间复杂度 O(n * C), C = 10, 用 substring 来截取字符串
 * 空间复杂度 O(n)
 * --------------------------------------------------------
 * 算法：位运算
 * 'A' - 00, 'C' - 01, 'G' - 10, 'T' - 11
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */
public class _08_187 {
    public static void main(String[] args) {
        String s = "123";
        System.out.println(s.substring(1, 2));
    }

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>(8);
        for (int i = 0; i <= s.length() - 10; i++) {
            final String tmp = s.substring(i, i + 10);
            final Integer cnt = map.getOrDefault(tmp, 0);
            if (cnt == 1) ans.add(tmp);
            map.put(tmp, cnt + 1);
        }
        return ans;
    }

    // 使用两位二进制表示字符
    Map<Character, Integer> bin = new HashMap<Character, Integer>(){{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};
    int L = 10;
    public List<String> findRepeatedDnaSequences_perfect(String s) {
        int len = s.length();
        List<String> ans = new ArrayList<>();
        if (len <= L) return ans;
        // 先计算出第一个长度为 10 的字串
        int x = 0;
        for (int i = 0; i < L; i++) x = (x << 2) | bin.get(s.charAt(i));
        Map<Integer, Integer> map = new HashMap<>();
        map.put(x, 1);
        for (int i = 1; i <= len - L; i++) {
            // & 是因为只用 20 位，其余要置为 0
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) == 2) ans.add(s.substring(i, i + 10));
        }
        return ans;
    }

}
